﻿\subsection{并发控制}

在引入多线程调度之后，若干线程之间的执行顺序上的随机性引入了数据竞争问题。
在本设计中，数据争用主要体现在对物理内存池、内核页表、显存等资源的并发访问上。
控制由线程并发产生的问题最主要的手段是加锁，根据锁的特点，可将锁分为自旋锁（Spin Lock）和互斥锁（Mutex Lock），
二者主要的区别在于取锁失败是否引发线程切换。
当线程尝试获取自旋锁时，若取锁失败，则当前线程会一直循环尝试取锁直至成功或时间片耗尽被换下处理器；
当线程尝试获取互斥锁时，一旦取锁失败，则立刻触发线程切换，主动将自己挂起。

这两种基础的锁各有优劣，自旋锁会导致 CPU 空转浪费时间片，但一旦取锁成功，则线程可以立即进入临界区；
互斥锁虽然避免了长时间的 CPU 空转，但线程切换的开销并不比 CPU 空转更少。

操作系统中的加锁需要兼顾效率和正确性，本设计中仅就实现自旋锁进行讨论。

\subsubsection{自旋锁}

x86 中为部分指令提供了 \lstinline{lock} 前缀，当 CPU 执行到具有 \lstinline{lock} 前缀的指令时，会在处理器中拉起 \lstinline{LOCK#} 信号，保证在指令执行过程中能够独占地访问的内存单元（或 Cache 块）。
在可添加 \lstinline{lock} 前缀的指令中，位检测指令 \lstinline{bts}、\lstinline{btr} 及比较交换指令 \lstinline{cmpxchg}（Intel 80486 后提供）等是常见的用于实现原子操作的指令。
鉴于位检测指令具有很好的兼容性，本设计中基于 \lstinline{btr} 指令实现自旋锁。

\lstinline{lock btr} 指令以原子方式将二进制串中的指定位保存在 \lstinline{EFLAGS.CF} 中，并将该位清零。
该过程相当于原子地将手中的 “0” 与二进制串中的位进行交换。
若线程发现交换之后 \lstinline{EFLAGS.CF} 中得到了“1”，则表明取锁成功，对应地，二进制串中的位被替换为“0”，表明此时为加锁状态；
否则取锁失败，二进制串中的位仍为“0”，临界区仍处于加锁状态。

在使用 \lstinline{lock btr} 取锁前后，还有诸多细节需要处理。
首先，尝试取锁之前，CPU 核心必须处于关中断状态，否则在取锁过程中发生线程调度，导致取锁操作结束后线程被换下处理器，另一线程的取锁操作将永远无法成功，进而引发死锁。
其次，在结束对临界区的访问，将锁归还后，还要将 \lstinline{EFLAGS.IF} 的值恢复到关中断之前的状态，因而在取锁关中断前需将 \lstinline{EFLAGS.IF} 在关中断之前予以保存，
该流程对应于 \lstinline{EFLAGS.IF} 的压栈和出栈操作。

某一线程在执行过程中可能连续执行多次取锁操作，对应于多次 \lstinline{EFLAGS.IF} 压栈。对应地，还锁时需要进行相反顺序的出栈。
在第一次取锁关闭中断后，此后压栈的 \lstinline{EFLAGS.IF} 均为 0，因而该过程可进一步简化为保存第一次取锁时的 \lstinline{EFLAGS.IF}，随后的若干次取锁过程中累计取锁次数（图 \ref{AQUIRE_LOCK}）。
在还锁过程中，每还一把锁，将取锁次数减一，直到取锁次数减少为 0 时，将保存的 \lstinline{EFLAGS.IF} 恢复为取锁前的初始状态（图 \ref{RELEASE_LOCK}）。

\begin{figure}[h!]
    \Centering
    \caption{取锁操作}
    \label{AQUIRE_LOCK}
    \includegraphics[scale=0.8]{build/Paper/Assets/AquireLock.pdf}
\end{figure}

\begin{figure}[h!]
    \Centering
    \caption{还锁操作}
    \label{RELEASE_LOCK}
    \includegraphics[scale=0.8]{build/Paper/Assets/ReleaseLock.pdf}
\end{figure}
